Depth First Search

깊이 우선 탐색(Depth First Search)
탐색을 함에 있어 깊은 것을 우선적으로 하여 탐색하는 알고리즘이다.
깊이 우선 탐색은 기본적으로 전체 노드를 맹목적으로 탐색하고자 할 때, 사용한다.
깊이 우선 탐색 알고리즘은 스택(Stack) 자료구조에 기초

깊이 우선 탐색은 빠르게 모든 경우의 수를 탐색할 때 사용

깊이 우선 탐색 알고리즘은 스택(Stack) 자료 구조에 기초한다는 점에서 구현이 간단하다.
재귀함수를 통해 탐색을 수행하는데 있어서 O(N)의 시간이 소요된다.
깊이 우선 탐색 과정
1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에서 방문하지 않은 인접 노드가 하나라도 있으면, 그 노드를 스택에 넣고 방문 처리한다.
    방문 하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 1001
typedef struct {
int index;
struct Node *next;
}Node;
Node **a;
int n, m, c[MAX_SIZE];
void addFront(Node *root, int index){
Node *node=(Node*)malloc(sizeof(Node));
node->index=index;
node->next=root->next;
root->next=node;
}
void dfs(int x){
if(c[x])return;
c[x]=1;
printf("%d ",x);
Node *cur =a[x]->next;
while(cur!=NULL){
int next=cur->index;
dfs(next);
cur=cur->next;
}
}
int main(void){
scanf("%d %d", &n, &m);
a=(Node**)malloc(sizeof(Node*)*(MAX_SIZE));
for(int i=1;i<=n;i++){
a[i]=(Node*)malloc(sizeof(Node));
a[i]->next=NULL;
}
for(int i=0;i<m;i++){
int x, y;
scanf("%d %d", &x, &y);
addFront(a[x],y);
addFront( a[y],x);
}
dfs(1);
system("pause");
return 0;
}